#include <bits/stdc++.h>

using namespace std;

// 滑动窗口最大值（单调队列经典用法模版）
// 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧
// 你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
// 返回 滑动窗口中的最大值 。
// 测试链接 : https://leetcode.cn/problems/sliding-window-maximum/

class Solution 
{
private:
    static const int MAXN = 100001;
    int q[MAXN];
    int h, t;

public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) 
    {
        h = t = 0;
        int n = nums.size();
        // 先形成长度为 k - 1 的窗口
        for(int i = 0; i < k - 1; ++i)
        {
            // 大 -> 小
            while(h < t && nums[q[t - 1]] <= nums[i]) --t;
            q[t++] = i;
        }

        int m = n - k + 1;
        vector<int> ans(m);
        // 当前窗口 k - 1 长度
        for(int l = 0, r = k - 1; l < m; ++l, ++r)
        {
            // 少一个，要让 r 位置的数进来
            while(h < t && nums[q[t - 1]] <= nums[r]) --t;
            q[t++] = r;
            // 收集答案
            ans[l] = nums[q[h]];
            // l 位置的数出去
            if(q[h] == l) ++h;
        }
        
        return ans;
    }
};


class Solution 
{
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) 
    {
        deque<int> q;
        // 形成长度为 k 的窗口
        for(int i = 0; i < k; ++i)
        {
            while(!q.empty() && nums[i] >= nums[q.back()]) q.pop_back();
            q.push_back(i);
        }
        int n = nums.size();
        vector<int> ret = {nums[q.front()]};
        for(int i = k; i < n; ++i)
        {
            while(!q.empty() && nums[i] >= nums[q.back()]) q.pop_back();
            q.push_back(i);
            while(q.front() + k <= i) q.pop_front();
            ret.push_back(nums[q.front()]);
        }
        return ret;
    }
};